#ifndef BINARYTREE
#define BINARYTREE
template<typename TValue>
class BinaryTree
{
public:
    enum class ChildSide { Left, Right,	};
    using Side = ChildSide;
    using ValueType = TValue;
private:
    BinaryTree* pLeft;
    BinaryTree* pRight;
    BinaryTree* pBase;
    Side side;// 指示自己是双亲的哪个孩子，仅当pBase不为null时有意义；不应由自己修改，而应由双亲修改
    int count;
public:
    TValue Value;
public:
    // 构造只有一个节点的树，并且元素为默认值
    BinaryTree();
    // 用指定值构造只有一个节点的树
    BinaryTree(const TValue& value);
    // 构造一个树，根节点的元素为指定值，并指定一个子树
    BinaryTree(const TValue& value, BinaryTree* pChild, Side side);
    // 构造一个树，根节点的元素为指定值，并指定左右两个子树
    BinaryTree(const TValue& value, BinaryTree* pLChild, BinaryTree* pRChild);
    // 析构该树及其所有子树
    ~BinaryTree();
    BinaryTree(const BinaryTree&) = delete;
    // 接管一个树，被接管的树成为一个孤立的节点
    BinaryTree(BinaryTree&& other);
    // 获取该树的双亲的指针
    BinaryTree* Parent() const;
    // 获取左子树的指针
    BinaryTree* LeftChild() const;
    // 获取右子树的指针
    BinaryTree* RightChild() const;
    // 获取节点总数
    int Count() const;
    // 获取树到最叶子节点的最大深度
    int DepthToLeaf() const;
    // 获取树到根节点的最大深度
    int DepthFromRoot() const;
    // 指示自己是否为叶子节点
    bool IsLeaf() const;
    // 指示自己是双亲的哪个孩子，仅当pBase不为null时有意义
    Side SideOfParent() const;
    // 设置指定子树，先前的子树会被析构
    void SetChild(BinaryTree* pChild, Side side);
    // 删除指定子树，将其析构
    void RemoveChild(Side side);
    // 移除指定子树，但不会析构该子树，而是返回指向它的指针
    BinaryTree* ReleaseChild(Side side);
    BinaryTree* ReleaseChild(BinaryTree* pChild);
};

template<typename TValue>
BinaryTree<TValue>::BinaryTree()
{
    this->pLeft = nullptr;
    this->pRight = nullptr;
    this->pBase = nullptr;
    this->count = 1;
    this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value)
{
    this->pLeft = nullptr;
    this->pRight = nullptr;
    this->pBase = nullptr;
    this->Value = value;
    this->count = 1;
    this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value, BinaryTree* pChild, Side side)
{
    switch (side)
    {
    case Side::Left:
    {
        this->pLeft = pChild;
        pChild->side = Side::Left;
        this->pRight = nullptr;
        break;
    }
    case Side::Right:
    {
        this->pRight = pChild;
        pChild->side = Side::Right;
        this->pLeft = nullptr;
        break;
    }
    default:
        break;
    }
    pChild->pBase = this;
    this->Value = value;
    this->count = 1 + pChild->count;
    this->pBase = nullptr;
    this->side = Side::Left;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(const TValue& value, BinaryTree* pLChild, BinaryTree* pRChild)
{
    this->pLeft = pLChild;
    pLChild->side = Side::Left;
    this->pRight = pRChild;
    pRChild->side = Side::Right;
    this->pBase = nullptr;
    pLChild->pBase = this;
    pRChild->pBase = this;
    this->Value = value;
    this->count = 1 + pLChild->count + pRChild->count;
}

template<typename TValue>
BinaryTree<TValue>::~BinaryTree()
{
    delete this->pLeft;
    delete this->pRight;
}

template<typename TValue>
BinaryTree<TValue>::BinaryTree(BinaryTree&& other)
{
    this->pBase = other.pBase;
    this->pLeft = other.pLeft;
    this->pRight = other.pRight;
    this->count = other.count;
    this->side = other.side;
    this->Value = other.Value;
    if (this->pLeft != nullptr)
    {
        this->pLeft->pBase = this;
    }
    if (this->pRight != nullptr)
    {
        this->pRight->pBase = this;
    }
    if (this->pBase != nullptr)
    {
        switch (this->side)
        {
        case Side::Left:
        {
            this->pBase->pLeft = this;
            break;
        }
        case Side::Right:
        {
            this->pBase->pRight = this;
            break;
        }
        default:
            break;
        }
    }
    other.pBase = nullptr;
    other.pLeft = nullptr;
    other.pRight = nullptr;
    other.count = 1;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::Parent() const
{
    return this->pBase;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::LeftChild() const
{
    return this->pLeft;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::RightChild() const
{
    return this->pRight;
}

template<typename TValue>
int BinaryTree<TValue>::Count() const
{
    return this->count;
}

template<typename TValue>
int BinaryTree<TValue>::DepthToLeaf() const
{
    int leftDepth = 0, rightDepth = 0;
    if (this->LeftChild() != nullptr)
    {
        leftDepth = this->LeftChild()->DepthToLeaf();
    }
    if (this->RightChild() != nullptr)
    {
        rightDepth = this->RightChild()->DepthToLeaf();
    }
    if (leftDepth >= rightDepth)
    {
        return leftDepth + 1;
    }
    else
    {
        return rightDepth + 1;
    }
}

template<typename TValue>
int BinaryTree<TValue>::DepthFromRoot() const
{
    int depth = 0;
    BinaryTree<TValue>* pTree = this;
    while (pTree->pBase != nullptr)
    {
        ++depth;
        pTree = pTree->pBase;
    }
    return depth;
}

template<typename TValue>
bool BinaryTree<TValue>::IsLeaf() const
{
    return this->pLeft == nullptr && this->pRight == nullptr;
}

template<typename TValue>
typename BinaryTree<TValue>::Side BinaryTree<TValue>::SideOfParent() const
{
    return this->side;
}

template<typename TValue>
void BinaryTree<TValue>::SetChild(BinaryTree* pChild, Side side)
{
    switch (side)
    {
    case Side::Left:
    {
        if (this->pLeft != nullptr)
        {
            this->count -= this->pLeft->count;
            delete this->pLeft;
            this->pLeft = nullptr;
        }
        if (pChild != nullptr)
        {
            this->pLeft = pChild;
            pChild->pBase = this;
            pChild->side = Side::Left;
            this->count += pChild->count;
        }
        break;
    }
    case Side::Right:
    {
        if (this->pRight != nullptr)
        {
            this->count -= this->pRight->count;
            delete this->pRight;
            this->pRight = nullptr;
        }
        if (pChild != nullptr)
        {
            this->pRight = pChild;
            pChild->pBase = this;
            pChild->side = Side::Right;
            this->count += pChild->count;
        }
        break;
    }
    default:
        break;
    }
}

template<typename TValue>
void BinaryTree<TValue>::RemoveChild(Side side)
{
    switch (side)
    {
    case Side::Left:
    {
        if (this->pLeft != nullptr)
        {
            this->count -= this->pLeft->count;
            delete this->pLeft;
            this->pLeft = nullptr;
        }
        break;
    }
    case Side::Right:
    {
        if (this->pRight != nullptr)
        {
            this->count -= this->pRight->count;
            delete this->pRight;
            this->pRight = nullptr;
        }
        break;
    }
    default:
        break;
    }
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::ReleaseChild(Side side)
{
    BinaryTree* pTree = nullptr;
    switch (side)
    {
    case Side::Left:
    {
        if (this->pLeft != nullptr)
        {
            this->count -= this->pLeft->count;
            pTree = this->pLeft;
            this->pLeft = nullptr;
        }
        break;
    }
    case Side::Right:
    {
        if (this->pRight != nullptr)
        {
            this->count -= this->pRight->count;
            pTree = this->pRight;
            this->pRight = nullptr;
        }
        break;
    }
    default:
        break;
    }
    if (pTree != nullptr)
    {
        pTree->pBase = nullptr;
    }
    return pTree;
}

template<typename TValue>
BinaryTree<TValue>* BinaryTree<TValue>::ReleaseChild(BinaryTree* pChild)
{
    if (pChild == nullptr)
    {
        return nullptr;
    }
    if (pChild->pBase != this)
    {
        return nullptr;
    }
    return this->ReleaseChild(pChild->side);
}

#endif // !BINARYTREE
